Surface modeling is a fundamental task in computer graphics, computer aided design (CAD), computer aided geometric design (CAGD), and computer animation. Surfaces are typically approximated by a mesh of polygons or piecewise polynomial patches. Because of their simplicity, polygonal meshes are a popular way to approximate surfaces and are adequate for many applications. A drawback of polygonal meshes is that they are inherently faceted, and a large number of polygons may be needed to make the facets small enough to satisfy the demands of the application.
In contrast, a popular smooth surface representation is tensor product B-spline surfaces. The control points for a B-spline surface are required to be topologically arranged in a rectangular grid. B-spline surfaces are comprised of several parametric surface patches that can be represented in Bézier form. A significant advantage of B-spline surfaces is that each of the constituent surface patches are automatically Cn−1 with its neighboring patches, where n is the degree of the basis functions.
The parameter values at which the constituent surface patches begin and end are called knots, and a non-decreasing sequence of knots is called a knot vector. A B-spline surface definition includes two knot vectors, one for each parameter of the parametric equation. In a uniform B-spline surface, the difference between each pair of knots in a given knot vector is constant. A non-uniform B-spline does not have such a constraint. A rational B-spline surface is one for which the control points are assigned weights. Weights provide additional shape control, allow the introduction of sharp creases in the model, and empower the B-spline surface to represent quadric surfaces. A non-uniform rational B-spline surface is referred to by the acronym NURBS surface.
Refinement of a NURBS control grid is accomplished through a procedure called knot insertion whereby one or more new knot values are inserted into a knot vector. Knot insertion does not alter the surface, but it provides more control points with which the designer can manipulate the model. Because NURBS control points must lie topologically in a rectangular grid, knot insertion causes one or more entire rows of control points to be added to the control grid. Cartesian coordinates for those new rows of control points along with some of the neighboring control points can be found such that the refinement operation does not alter the surface. Unfortunately, adding an entire row of control points for each desired new control point simply to satisfy the rectangular grid topology of NURBS surfaces increases the modeling complexity of the surface dramatically.
Surface refinement is a valuable operation that has several uses. First of all, refinement allows a designer to insert additional control points into a surface region where more detail is called for in the model. For example, more control points would be needed using NURBS to model a human ear than to model a cheek. Second, each time a control grid is refined, the control grid itself becomes an increasingly better approximation of the NURBS surface that it defines. Thus, by performing repeated refinements, the control grid can become an arbitrarily accurate representation of the surface, which is suitable for rendering. Third, knot insertion can be used to compute the control points of the Bézier patches that comprise a NURBS. Fourth, sharp features can be added to NURBS surfaces using knot insertion. NURBS surfaces are generally Cn−1 continuous, where n is the degree of the surface. However, if r identical knots exist in a knot vector, the surface is Cn−r at that knot value. Thus, a triple knot in a cubic NURBS surface permits a C0 crease. Uniform B-spline surfaces do not allow arbitrary knot insertion, for as soon as a single knot is inserted, the surface becomes a non-uniform B-spline surface. The only knot insertion possible for a uniform B-spline surface (if it is to remain uniform after the knot insertion) is to simultaneously insert a knot midway between each pair of neighboring knots, a process called knot doubling. Since uniform B-splines cannot support two or more identical knots, uniform B-spline surfaces are always Cn−1 continuous and it is not possible to impose a C0 crease.
Several algorithms exist for knot insertion. The Oslo algorithm computes so-called discrete B-splines to define the B-spline basis transformation from a refined space of splines to a subspace. Another method of knot insertion is Boehm's algorithm which works directly with the B-spline coefficients. In addition, mathematical insights like the blossoming principle for knot insertion have been developed.
Knot removal, the inverse operation of knot insertion, can also be performed on NURBS. By comparison, knot insertion does not modify the surface, while knot removal in general does alter the surface. Therefore, knot removal usually involves approximation. One motivation for knot removal is data reduction. The problem is to minimize the number of knots subject to an error tolerance. Another application of knot removal is shape fairing. The continuity order can be increased by removing knots.
The requirement that all control points for a NURBS surface must topologically be positioned in a rectangular grid is a serious shortcoming. There are at least three reasons why this is a problem. First, surfaces of arbitrary topology can be represented using NURBS surfaces only by partitioning the model into a collection of individual NURBS patches. Adjacent patches are then explicitly stitched together using geometric continuity conditions. FIG. 2 shows a hand model comprised of seven NURBS surfaces. The small rectangular area is magnified in FIG. 3 to show a hole where neighboring NURBS surfaces do not match exactly. The presence of such gaps places a burden on modelers who potentially must repair a widened gap whenever the model is deformed.
A second reason why this constraint is so serious is because it typically means that a large number of NURBS control points serve no purpose other than to satisfy topological constraints. They carry no significant geometric information. Superfluous control points are a serious nuisance for designers, not merely because they require the designer to deal with more data, but also because they can introduce unwanted ripples in the surface. FIG. 1 shows a NURBS head model. Designers can waste dozens of hours on models, such as FIG. 1, in tweaking the NURBS control points while attempting to remove unwanted ripples. The darker NURBS control points are superfluous (as will be later shown in the present invention) and have been added as the result of including control points desired by the modeler that resulted in additional rows of control points.
A third reason why the rectangular grid constraint is a problem is that it is not possible to insert a single control point into a NURBS control grid, but rather, an entire row of control points must be added each time a single knot insertion is performed. This means that true local refinement of NURBS surfaces is not possible, since the insertion of a single control point demands the insertion of an entire row into the control grid.
In order to further illustrate the complexities of solving the problems associated with NURBS, one attempt at solving this problem will now be addressed. In August 2001, Almaz Bakenov completed a master's thesis at Brigham Young University entitled, “T-splines: Tensor Product B-spline Surfaces with T-Junctions”. Thomas W. Sederberg, the inventor of the present invention described later in the detailed description, was the advisor for Almaz Bakenov's thesis. The Bakenov thesis represents an early attempt at resolving the problems associated with NURBS. Indeed, Thomas W. Sederberg wrestled with this problem from 1999 to 2003. Thus, we have the slightly confusing situation in which there are two significantly different concepts called T-splines: the concept later described in the present invention, and the notion of T-splines described in the Bakenov thesis.
Particularly, the notion of T-splines presented in the Bakenov thesis contains limitations that render it almost useless. Most significantly, the T-splines described in the Bakenov thesis are not capable of solving the problems associated with NURBS without the solution of a potentially huge system of linear equations, for which a solution does not exist in many cases. For these reasons, the notion of T-splines contained in the Bakenov thesis is of little practical value.
Several surface formulations have been proposed that do not suffer from NURBS' topological constraint of requiring all control points to lie in a rectangular grid. The arbitrary-topology surface formulation that is most pertinent to the present discussion is called a subdivision surface. Catmull-Clark subdivision surfaces are, in fact, generalizations of B-spline surfaces. When the control points of a Catmull-Clark surface happen to lie topologically in a rectangular grid, the surface degenerates to a bicubic uniform B-spline surface. In like manner, Doo-Sabin subdivision surfaces generalize biquadratic uniform B-spline surfaces to control grids of arbitrary topology.
Refinement of a Catmull-Clark surface is based on the notion of knot doubling for uniform bicubic B-spline surfaces, with special rules introduced to handle non-four-sided faces and non-valence-four vertices. With each refinement step, the number of faces grows by a factor of four. Repeated refinement causes the control grid to approximate the limit surface ever more closely.
A problem with Catmull-Clark surfaces is that, since they are based on uniform B-spline surfaces, it is not possible to represent sharp C0 features. However, some methods have been proposed for defining sharp features, edges, creases, and corners into subdivision surfaces by altering the refinement rules in the neighborhood of such features.
Another more serious problem is that local refinement of Catmull-Clark surfaces is not possible. In fact, where the simplest refinement operation for a NURBS surface is to insert a single row of control points, only a global refinement operation is defined for Catmull-Clark surfaces, and the number of control points grows by roughly a factor of four with each refinement step.